#! /usr/bin/env python
# -*- coding: utf-8 -*-

class Solution:
    """
    @param matrix: matrix, a list of lists of integers
    @param target: An integer
    @return: a boolean, indicate whether matrix contains target
    """
    def searchMatrix(self, matrix, target):
        # write your code here
        # 方式1, matrix ------> array

        # 方式2, map array ------> matrix

        # 方式3, 直接搜索矩阵
        if not matrix:
            return False

        self.matrix = matrix
        self.rows, self.cols = len(matrix), len(matrix[0])
        self.min, self.max = matrix[0][0], matrix[self.rows-1][self.cols-1]

        row, is_find = self.search_row(target)
        print(row, is_find)
        if row is None:
            return False
        else:
            if is_find:
                return True
            else:
                return self.search_detail(row, target)

    def search_row(self, value):
        '''
        return row, exact_find?
        '''
        if value < self.min or value > self.max:
            return None, None

        start, end = 0, self.rows   # [start, end)

        while start < end:
            mid = (start + end) // 2
            mid_value = self.row(mid)
            print(start, end, mid, mid_value)
            # 0, 1, 0, 1

            if end - start == 1:
                return start, False

            if value < mid_value:
                end = mid
            elif value > mid_value:
                start = mid     # 注意这里不能 +1, 因为元素可能在当前行
            else:
                return mid, True

        return start, False

    def search_detail(self, row, value):
        l = self.matrix[row]
        start, end = 0, self.cols

        while start < end:
            mid = (start + end) // 2
            mid_value = l[mid]
            # 0, 1, 0, 1

            # if end - start == 1:
            #     return start, False

            if value < mid_value:
                end = mid
            elif value > mid_value:
                start = mid + 1
            else:
                return True

        return False


    def row(self, row):
        return self.matrix[row][0]


def main():
    print("start main")

    mat = [
        [1, 3, 5, 7],
        [10, 11, 16, 20],
        [23, 30, 34, 50]
    ]

    mat = [
        [1,5,10,11,16,23,24,26,29,34,41,48,49,56,63,67,71,74,75],
        [97,118,131,150,160,182,202,226,251,273,289,310,326,349,368,390,401,412,428],
        [445,455,466,483,501,519,538,560,581,606,631,643,653,678,702,726,748,766,781],
        [792,817,837,858,872,884,901,920,936,957,972,982,1001,1024,1044,1063,1086,1098,1111],
        [1129,1151,1172,1194,1213,1224,1234,1250,1267,1279,1289,1310,1327,1348,1371,1393,1414,1436,1452],
        [1467,1477,1494,1510,1526,1550,1568,1585,1599,1615,1625,1649,1663,1674,1693,1710,1735,1750,1769]
    ]


    s = Solution()
    r = s.searchMatrix(mat, 1086)
    print(r)

if __name__ == "__main__":
    main()
